#include<tools_node.h>
#include<stdio.h>
int node_size(Node* node)
{
    if(node==NULL)
    {
        return 0;
    }
	Node*node1=(Node*)(node->Prev);
	int i=0;
    while(node!=NULL)
    {
        node=(Node*)node->Next;
        i++;
    }
	int j=0;
	while(node1!=0)
	{
		node1=(Node*)(node1->Prev);
		j++;
	}
    return i+j;
}
Node* node_at(Node*node ,int i)
{
    int size=node_size(node);
    int j=(i+size)%size;
    Node*nit=node;
    for(int k=0;k<j;k++)
    {
        nit=(Node*)(nit->Next);
    }
    return nit; 
}
void free_node(Node *node)
{	
	if(node==NULL)
	{return;}

    Node* node1=node->Next,*node2=node->Prev,*iter;
    while(node1!=NULL)
    {
	iter=node1->Next;
        free(node1);
        node1=iter;
    }
	while(node2!=NULL)
	{
		iter=node2->Prev;
		free(node2);
		node2=iter;
	}
	free(node);
}
void free_node_value(Node *node)
{
 	if(node==NULL)
	{return;}

    Node* node1=node->Next,*node2=node->Prev,*iter;
    while(node1!=NULL)
    {
	iter=node1->Next;
        free(node1->value);
        node1=iter;
    }
	while(node2!=0)
	{
		iter=node2->Prev;
		free(node2->value);
		node2=iter;
	}
	free(node->value);

}
Node* node_find(Node* node,void* value)
{
	Node* re=node;
    while(re!=NULL)
    {
        if(re->value==value)
        {break;}
        re=(Node*)(re->Next);
    }
    return re;
}
//
Node* node_copy(Node* node)
{
	if(node==NULL)
	{
	return NULL;
	}
	Node* node1=(Node*)malloc(sizeof(Node));
	Node* node2=node1;
	Node_init(node1);
    while(node!=NULL)
    {
	    node2->value=node->value;
        node2->traits=node->traits;
	    node=(Node*)node->Next;
	    if(node==NULL)
	    {
	        break;
	    }
        Node* node3=(Node*)malloc(sizeof(Node));
	    Node_init(node3);
	    node2->Next=(void*)node3;
	    node3->Prev=(void*)node2;
	    node2=node3;
    }

    return node1;
}



Node* node_reverse(Node*node)
{
	if(node==NULL)
	{return NULL;}
	else
	{
		if(node->Next!=NULL)
		{
			while(node->Next!=NULL)
			{
				node=(Node*)node->Next;
			}
			return node;
		}
		else
		{
			while(node->Prev!=NULL)
			{
				node=(Node*)node->Prev;

			}
			return node;
		}	
	}
    return NULL;
}
Node* node_reversen(Node*node)
{
    Node* re=NULL;
    if(node->Next!=NULL)
    {
        for(Node* nit=node;nit!=NULL;nit=(Node*)(nit->Next))
        {
            re=node_overlying(re,nit->value);
        } 
    }
    
    return re;


}



Node* node_union(Node*n1,Node*n2)
{
    Node* re=node_copy(n1); 
    for(Node* nit=n2;nit!=NULL;nit=(Node*)(nit->Next)) 
    {
        if(node_find(re,nit->value)==NULL) 
        {
            re=node_overlying(re,nit->value); 
        } 
    } 
    return re;

}
Node* node_intersection(Node* n1,Node* n2)
{
    Node* re=NULL;
    for(Node* nit=n2;nit!=NULL;nit=(Node*)(nit->Next))
    {
        if(node_find(n1,nit->value)!=NULL)
        {
            re=node_overlying(re,nit->value);
        }
    }
    return re;
}
Node* node_minus(Node* n1,Node* n2)
{
    Node* re=node_copy(n1);

    for(Node* nit=n2;nit!=NULL;nit=(Node*)(nit->Next))
    {
        re=node_delete_value(re,nit->value);
    }
    
    return re;
}
Node* node_bub_sort(Node* n,int (*cmp)(void* a,void* b))
{
    Node* nit=node_reverse(n);
    while(nit!=n)
    {
        Node* nit1=(Node*)(nit->Prev);

        void* v1=nit->value,*v2=nit1->value;
        if(cmp(nit->value,nit1->value)==1)
        {
            nit->value=v2;
            nit1->value=v1;     
        }

        nit=nit1;
    }

    return nit;
}

Node* node_bub_sortn(Node* n,int (*cmp)(void* a,void* b))
{
	Node* re=n;
	int flag=0;
	do{
		flag=0;
       // printf("once\n");
		Node* nit=re;
		while(nit!=NULL&&nit->Next!=NULL)
		{
			Node* nit1=(Node*)(nit->Next);
			if(cmp(nit1->value,nit->value)==1)
			{
               // printf("here\n");
				if(nit==re)
				{
					re=nit1;
				}
				nit1->Prev=nit->Prev;
				if(nit->Prev!=NULL)
				{
					((Node*)(nit->Prev))->Next=nit1;
				}
                nit->Next=nit1->Next;
                if(nit1->Next!=NULL)
                {
                    ((Node*)(nit1->Next))->Prev=nit;
                }
				nit1->Next=nit;
				nit->Prev=nit1;
				flag=1;
			}
            else
            {
                nit=nit1;
            }
		}
	}while(flag==1);
	return re;
}

Node* node_filter_condition(Node* n,int (*filter_condition)(void* a))
{

    Node*re=node_copy(n);
    Node* nit=re;
    while(nit!=NULL)
    {
        
        if(filter_condition(nit->value)==1)
        {
            if(nit==re)
            {
                re=(Node*)(re->Next);
            }
            Node* temp_nit=nit;
            nit=(Node*)(nit->Next);
            if(temp_nit->Prev!=NULL)
            {
                ((Node*)(temp_nit->Prev))->Next=nit;
            }
            if(nit!=NULL)
            {
                nit->Prev=temp_nit->Prev;
            }
            free(temp_nit);
        }
        else
        {
            nit=(Node*)(nit->Next);
        }
    }

    return re;
   
}
void ** node2array(Node*n)
{
    int len=node_size(n);
    void** re=(void**)malloc(sizeof(void*)*len);
    int i=0;
    for(Node* nit=n;nit!=NULL;nit=(Node*)(nit->Next))
    {
        re[i]=nit->value;
        i++;
    }
    return re;
}

static inline void swap(void** values,int left,int right)
{
    void* temp=values[left];
    values[left]=values[right];
    values[right]=temp;
}

static void sort_values(void** values,int left,int right,int (*cmp)(void* a,void* b))
{
    if(left>=right)
    {
        return;
    }
    int m=left;
    for (int i=left+1;i<=right;i++)
    {
        if(cmp(values[left],values[i]))
        {
            swap(values,++m,i);
        } 
    }   
    swap(values,left,m);  
    sort_values(values,left,m-1,cmp);  
    sort_values(values,m+1,right,cmp);
}

Node* node_quick_sort(Node* n,int (*cmp)(void* a,void* b))
{
    int len=node_size(n);
    void**values=(void**)malloc(sizeof(void*)*len);
    int i=0;
    for(Node* nit=n;nit!=NULL;nit=(Node*)(nit->Next))
    {
        values[i]=nit->value;i++;
    }
    sort_values(values,0,len-1,cmp);
    Node* re=NULL;
    for(i=0;i<len;i++)
    {
        re=node_pushback(re,values[i]);
    }

    free(values);
    return node_reverse(re);
 
}
Node* array2node(void**data,int len)
{
    Node* re=NULL;
    for(int i=0;i<len;i++)
    {
        re=node_pushback(re,data[i]);
    }
    return node_reverse(re);

}
Node* unique_node(Node* n)
{
    void **data= node2array(n);
    int len =node_size(n);
    int mark=0;

    while(mark<len-1)
    {
        for(int i=len-1;i>mark;i--)
        {   
            if(data[i]==data[mark])
            {
                data[mark]=data[len-1];
                len--;
            }
        }
        mark++;
    }
    Node* re= array2node(data,len);
    free(data);
    return re;
   
}